def max_subsequence(arr, start, end):
    if start == end:
        return arr[start]
    mid = (start + end) // 2
    left_sum = max_subsequence(arr, start, mid)
    right_sum = max_subsequence(arr, mid + 1, end)
    cross_sum = cross_subsequence(arr, start, mid, end)
    return max(left_sum, right_sum, cross_sum)


def cross_subsequence(arr, start, mid, end):
    left_sum = float('-inf')
    sum = 0
    for i in range(mid, start - 1, -1):
        sum += arr[i]
        if sum > left_sum:
            left_sum = sum
    right_sum = float('-inf')
    sum = 0
    for i in range(mid + 1, end + 1):
        sum += arr[i]
        if sum > right_sum:
            right_sum = sum
    return left_sum + right_sum


# 测试
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subsequence(arr, 0, len(arr) - 1))
